class Solution(object):
    def smallestEquivalentString(self, s1, s2, baseStr):
        """
        :type s1: str
        :type s2: str
        :type baseStr: str
        :rtype: str
        """
        d = {}
        n = len(s1)

        def find(x):
            if d[x] == x:
                return x
            else:
                d[x] = find(d[x])
                return d[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    d[rooty] = rootx
                else:
                    d[rootx] = rooty

        for i in range(n):
            if s1[i] not in d:
                d[s1[i]] = s1[i]
            if s2[i] not in d:
                d[s2[i]] = s2[i]
            union(s1[i], s2[i])

        out = ''
        for i in range(len(baseStr)):
            if baseStr[i] in d:
                out += find(baseStr[i])
            else:
                out += baseStr[i]
        return out